/*
 * @lc app=leetcode.cn id=315 lang=java
 *
 * [315] 计算右侧小于当前元素的个数
 */

import java.util.ArrayList;
import java.util.List;

// @lc code=start
class Solution {

    List<Integer> res = new ArrayList<>();
    int[] index;        // 索引数组;
    int[] count;

    public List<Integer> countSmaller(int[] nums) {
        int len = nums.length;
        index = new int[len];
        count = new int[len];

        for(int i = 0; i < len; i++) {
            index[i] = i;
        }

        MergeSort(nums, 0, nums.length - 1);
        for(int i = 0; i < len; i++) {
            res.add(count[i]);
        }
        return res;


    }

    private void MergeSort(int[] nums, int start, int end) {
        if(start < end) {
            int mid = start + (end - start) / 2;
            MergeSort(nums, start, mid);    // 划分无需数组
            MergeSort(nums, mid+1, end);
            merge(nums, start, mid, end);   // 合并有序数组
        }
    }

    private void merge(int[] nums, int start, int mid, int end) {
        int p1 = start, p2 = mid + 1;
        int cur = 0;
        int[] tmp = new int[end - start + 1];
        int[] tmpIndex = new int[end - start + 1];

        while(p1 <= mid && p2 <= end) {
            if(nums[p1] > nums[p2]) {
                count[index[p1]] += end - p2 + 1;
                tmpIndex[cur] = index[p1];
                tmp[cur] = nums[p1];
                p1++;
            } else {
                tmp[cur] = nums[p2];
                tmpIndex[cur] = index[p2];
                p2++;
            }
            cur++;
        }

        while(p1 <= mid) {
            tmp[cur] = nums[p1];
            tmpIndex[cur] = index[p1];
            p1++;
            cur++;
        }

        while(p2 <= end) {
            tmp[cur] = nums[p2];
            tmpIndex[cur] = index[p2];
            p2++;
            cur++;
        }

        for(int i = 0; i < end - start + 1; i++) {
            nums[i + start] = tmp[i];
            index[i + start] = tmpIndex[i];
        }
    }

}
// @lc code=end

